package com.dh.leetcode.two;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName: _205_isomorphic_strings
 * @Description: 205. 同构字符串
 * 给定两个字符串 s 和 t，判断它们是否是同构的。
 * <p>
 * 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
 * <p>
 * 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
 * <p>
 * 示例 1:-++++++++++++++++++++++
 * <p>
 * 输入: s = "egg", t = "add"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: s = "foo", t = "bar"
 * 输出: false
 * 示例 3:
 * <p>
 * 输入: s = "paper", t = "title"
 * 输出: true
 * 说明:
 * 你可以假设 s 和 t 具有相同的长度。
 * <p>
 * https://leetcode-cn.com/problems/isomorphic-strings/
 * @Author: shouzimu
 * @Date: 2020/12/28 4:06
 */
public class _205_isomorphic_strings {
    /**
     * 开辟一个空间存储映射关系
     *
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic(String s, String t) {
        if (null == s || null == t) {
            return false;
        }
        Map<Character, Character> mapping = new HashMap();
        Map<Character, Character> reverseMapping = new HashMap();

        char[] ms = new char[s.length()];
        char[] sa = s.toCharArray();
        char[] ta = t.toCharArray();
        Character c, d;
        for (int i = 0; i < sa.length; i++) {
            c = mapping.get(sa[i]);
            if (c == null) {
                c = ta[i];
            }
            mapping.put(sa[i], c);
            d = reverseMapping.put(c, sa[i]);
            if (null != d && d != sa[i]) {
                break;
            }
            ms[i] = c;
        }
        return new String(ms).equals(t);
    }

    @Test
    public void isIsomorphicTest() {
        Assert.assertEquals(false, isIsomorphic("aa", "ab"));
        Assert.assertEquals(true, isIsomorphic("ab", "cd"));
        Assert.assertEquals(true, isIsomorphic("egg", "add"));
        Assert.assertEquals(false, isIsomorphic("bar", "foo"));
        Assert.assertEquals(false, isIsomorphic("aba", "baa"));
        Assert.assertEquals(true, isIsomorphic("paper", "title"));
    }

}
